package algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU(least recently used)
 */
public class NO146_LRU缓存 {

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 0);
        lRUCache.put(2, 2);
        lRUCache.get(1);
        lRUCache.put(3, 3);
        lRUCache.get(2);
        lRUCache.put(4, 4);
        lRUCache.get(1);
        lRUCache.get(3);
        lRUCache.get(4);
    }


    static class LRUCache {

        /**
         * 快速查找节点 ，O(1)复杂度
         */
        Map<Integer, Node> cache;
        /**
         * 哨兵节点
         */
        Node head;
        Node tail;
        int capacity;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            cache = new HashMap<>();
        }

        public int get(int key) {
            // 如果存在，则放到链表最开头的位置，不存在返回null
            Node node = cache.get(key);
            if (node != null) {
                moveToHead(node);
            }
            return node == null ? -1 : node.value;
        }

        public void put(int key, int value) {
            // 小于容量，正常插入cache，并且放到链表的尾部，如果容量已经满，就删掉连表末尾的元素
            Node exist = cache.get(key);
            if (exist != null) {
                exist.value = value;
                moveToHead(exist);
                return;
            }

            // 如果多出，则需要进行淘汰
            Node newNode = new Node(key, value);
            if (cache.size() >= capacity) {
                Node eliminated = removeTail();
                cache.remove(eliminated.key);
            }
            cache.put(key, newNode);
            addToHead(newNode);
        }

        /**
         * 将节点添加到头部
         */
        private void addToHead(Node node) {
            Node originalFirst = head.next;
            head.next = node;
            node.prev = head;
            node.next = originalFirst;
            originalFirst.prev = node;
        }

        /**
         * 将节点从链表中删除
         */
        private void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        /**
         * 将存在的节点移动到头部(remove后直接重新add)
         */
        private void moveToHead(Node node) {
            remove(node);
            addToHead(node);
        }

        /**
         * 溢出最久未使用的节点
         */
        private Node removeTail() {
            Node deleted = tail.prev;
            remove(deleted);
            return deleted;
        }

        /**
         * 用来表示每一个数据项
         */
        private static class Node {
            int key;
            int value;
            Node prev;
            Node next;

            public Node() {
            }

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }
}
